import java.util.Arrays;

public class Test {

    public static void heapSort(int[] array) {
        if(array == null || array.length == 0) {
            return;
        }
        //建立大根堆
        creatHeap(array);

        //升序排列
        int end = array.length - 1;
        while(end > 0) {
            swap(array,0,end);
            siftDown(array,0,end);
            end--;
        }
    }

    private static void creatHeap(int[] array) {
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
            siftDown(array,parent,array.length);
        }
    }

    private static void siftDown(int[] array, int parent, int size) {
        int child = 2*parent + 1;
        while(child < size) {
            if(child + 1 < size && array[child+1] > array[child]) {
                child++;
            }
            if(array[parent] < array[child]) {
                swap(array,parent,child);
                parent = child;
                child = 2*parent + 1;
            } else {
                break;
            }
        }
    }

    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int mixIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if(array[j] < array[mixIndex]) {
                    mixIndex = j;
                }
            }
            swap(array,mixIndex,i);
        }
    }

    public static void selectSort2(int[] array) {
        int left = 0;
        int right = array.length - 1;
        while(left < right) {
            int minIndex = left;
            int maxIndex = left;
            for (int i = left + 1; i <= right; i++) {
                if(array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if(array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(array,left,minIndex);
            //如果maxIndex就是left所对应的数值，那么由于上面left已经和minIndex交换了，所以maxIndex要发生改变
            if(maxIndex == left) {
                maxIndex = minIndex;
            }
            swap(array,maxIndex,right);
            left++;
            right--;
        }
    }

    public static void quickSort(int[] array) {
        quick(array,0,array.length - 1);
    }

    private static void quick(int[] array, int left, int right) {
        if(left >= right) {
            return;
        }

        int pivot = partition(array,left,right);

        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }

    private static int partition(int[] array, int left, int right) {
        int tmp = array[left];
        int tmpLeft = left;
        while(left < right) {
            while(left < right && array[right] >= tmp) {
                right--;
            }

            while(left < right && array[left] <= tmp) {
                left++;
            }

            swap(array,left,right);
        }

        swap(array,tmpLeft,left);

        return left;
    }

    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {20,17,4,16,5,3};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
